class Solution {
    /*
        堆排序: 时间复杂度O(N)+O(KlogN)
    */
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length-1;
        for (int i = len / 2; i >= 0; i--) {
            flowDown(nums, i, len);
        }
        for (int i = 1; i < k; i++) {
            // 将最后一个元素移动到堆顶
            // System.out.println(nums[0]);
            nums[0] = nums[len];
            len --;
            flowDown(nums,0, len);
        }
        return nums[0];
    }

    public void flowDown(int[] nums, int i, int len) {
        while (i <= len) {
            int ii = i;
            int left = (i << 1) + 1, right = left + 1;
            if (left <= len && nums[left] > nums[i])
                i = left;
            if (right <= len && nums[right] > nums[i])
                i = right;
            if (i != ii) {
                int tmp = nums[i];
                nums[i] = nums[ii];
                nums[ii] = tmp;
            } else {
                break;
            }
        }
    }
}


class Solution {
    /*
        核心1: 每次快排都会确定一个元素的位置, 本来我们需要对左右两边都进行递归的, 但是可以只
            递归左边或者右边 提高效率
        核心2: 快排随机化 避免极端情况
    */
    int kk;
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        kk = nums.length-k;
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
        return nums[kk];
    }
    // 2 3 1
    public void quickSort(int[] nums, int left, int right) {
        if (left >= right)
            return;
        // 随机化
        int randomIndex = left + 1 + random.nextInt(right - left);
        int tmp2 = nums[randomIndex];
        nums[randomIndex] = nums[left];

        nums[left] = tmp2;
        int target = nums[left];
        int lleft = left, rright = right;
        while (left < right) {
            while (left < right && nums[right] >= target)
                right--;
            while (left < right && nums[left] <= target)
                left++;

            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }

        }
        nums[lleft] = nums[left];
        nums[left] = target;

        // index = lleft 的元素已经确定位置
        // 希望index=kk 的元素找到
        if(left==kk){
            return;
        }else if(kk < left){ // kk在左边
            quickSort(nums, lleft, left - 1);
        }else {              // kk在右边
            quickSort(nums, left + 1, rright);
        }
    }
}